#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义队列节点结构
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

// 创建一个新的队列节点
QueueNode* createQueueNode(TreeNode* node) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->treeNode = node;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
QueueNode* initQueue() {
    return NULL;
}

// 入队操作
void enqueue(QueueNode** front, QueueNode** rear, TreeNode* node) {
    QueueNode* newNode = createQueueNode(node);
    if (*rear == NULL) {
        *front = *rear = newNode;
    } else {
        (*rear)->next = newNode;
        *rear = newNode;
    }
}

// 出队操作
TreeNode* dequeue(QueueNode** front, QueueNode** rear) {
    if (*front == NULL) {
        return NULL;
    }
    QueueNode* temp = *front;
    TreeNode* node = temp->treeNode;
    *front = (*front)->next;
    if (*front == NULL) {
        *rear = NULL;
    }
    free(temp);
    return node;
}

// 判断队列是否为空
int isQueueEmpty(QueueNode* front) {
    return front == NULL;
}

// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    QueueNode* front = initQueue();
    QueueNode* rear = NULL;
    enqueue(&front, &rear, root);

    while (!isQueueEmpty(front)) {
        TreeNode* current = dequeue(&front, &rear);

        // 访问当前节点
        printf("%d ", current->value);

        // 入队左子节点
        if (current->left != NULL) {
            enqueue(&front, &rear, current->left);
        }

        // 入队右子节点
        if (current->right != NULL) {
            enqueue(&front, &rear, current->right);
        }
    }
}

// 创建一个新的树节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 主函数
int main() {
    // 创建树的节点
    TreeNode* root = createNode(1);
    TreeNode* node2 = createNode(2);
    TreeNode* node3 = createNode(3);
    TreeNode* node4 = createNode(4);
    TreeNode* node5 = createNode(5);

    // 手动构建二叉树
    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->right = node5;

    // 打印树的层次遍历结果
    printf("树的层次遍历结果: ");
    levelOrderTraversal(root);
    printf("\n");

    // 释放内存（省略具体实现）

    return 0;
}
